// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-15 13:22
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.DateTrain;

import org.junit.jupiter.api.Test;

import java.util.*;

public class CountMaxOrSubsets {
    /**
     * 状态保存+回溯
     */
    public int countMaxOrSubsetsT(int[] nums) {
        /*
            1 状态 -> 当前最大或值和最大或值子集数量
            2 状态转移 -> 当前或值 == 最大或值 || 当前或值 < 最大或者
         */
        int n = nums.length, max = Integer.MIN_VALUE, sum = 0;
        // 状态数组
        int[] dp = new int[2];
        // 状态初始化
        dp[0] = Integer.MIN_VALUE;
        List<Integer> stack = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            dfs(nums, i, n - 1, dp, stack);
        }
        return dp[1];
    }

    /**
     * 递归获取或值
     */
    private void dfs(int[] nums, int index, int end, int[] dp, List<Integer> stack) {
        if (index > end) {
            // 超出数组范围，后者当前值是自己，递归结束
            return;
        }
        stack.add(nums[index]);
        orMax(stack, dp, nums[index]);
        dfs(nums, index + 1, end, dp, stack);
        // 回溯
        stack.remove(stack.size() - 1);
    }

    /**
     * 子集判断方法
     *
     * @param stack: 当前的子集
     * @param dp:    状态变量
     * @param num    : 最新加入数据
     */
    private void orMax(List<Integer> stack, int[] dp, int num) {
        int orVal = 0;
        for (Integer next : stack) {
            orVal = (orVal | next);
        }
        if (orVal > dp[0]) {
            // 最大或值易主
            dp[0] = orVal;
            dp[1] = 0;
            ++dp[1];
        } else if (orVal == dp[0]) {
            ++dp[1];
        }
    }

    public int countMaxOrSubsets(int[] nums) {
        int n = nums.length, mask = 1 << n;
        int max = 0, ans = 0;
        for (int s = 0; s < mask; s++) {
            int cur = 0;
            for (int i = 0; i < n; i++) {
                if (((s >> i) & 1) == 1) {
                    cur |= nums[i];
                }
            }
            if (cur > max) {
                max = cur;
                ans = 1;
            } else if (cur == max) {
                ans++;
            }
        }
        return ans;
    }


    @Test
    public void shout() {
        int[] test = {3, 2, 1, 5};
        System.out.println(countMaxOrSubsets(test));
    }
}
